The present invention relates generally to the field of computer devices, and more specifically concerns a device for retrieving the particular one or more records from a data base comprising a large number of stored records which best satisfy a search specification established by a digital computer.
In U.S. Pat. No. 3,906,455 titled "Associative Memory Device", which has the same named inventor, and is assigned to the same assignee, as the present invention, apparatus is disclosed and claimed which is responsive to a request from a digital computer to locate and retrieve data stored in peripheral memory. Data is stored in peripheral memory in the form of logical records, which are in turn comprised of a number of data fields. The logical records are actually stored in data tracks which are individually addressable.
The retrieval process disclosed and claimed in the U.S. Pat. No. 3,906,455 uses a search specification, established by the digital computer, which designates one or more data fields as range fields and may designate one data field as a value field. Any particular field in a logical record may be a range field or a value field (the value field can also be range tested), depending on the search specification established by the digital computer. The search specification also establishes range field values and range field operators which are applied against the range fields, and perhaps the value field, of each logical record, and a value operator which is applied against the value field of each logical record in the data base being searched.
The permissible range operators are: (1) greater than; (2) less than; (3) greater than or equal to; (4) less than or equal to; (5) equality; and (6) inequality. One or two designated range operators are then used with the designated range value by the search apparatus against one selected range field (or the value field) in each logical record in the data base. All of the range tests are performed against one logical record before moving on to the next one.
The permissable value operators are: (1) greatest; and (2) least. The designated value operator for the value field is used by the search apparatus in its value field test of each logical record in the data base. A value test may or may not be specified, depending on the particular search specification being implemented. The particular record or records which best satisfy the range and value tests (if specified) are then returned to the using computer. A search of all the logical records comprising a data base in accordance with the search specification established by the digital computer is referred to as a general associative search. The structure and operation of the search apparatus which is capable of performing a general associative search, such as that discussed above, are disclosed in more detail in the U.S. Pat. No. 3,906,455.
In the U.S. Pat. No. 3,906,455, the peripheral memory comprising the area to be searched is disclosed to be divided into groups of data tracks, referred to as track groups. Referring now to FIG. 1 of the present invention, a plurality of data tracks 20--20 comprise a peripheral memory shown generally at 22. Peripheral memory 22 may be a conventional rotating disc or drum, or a more advanced peripheral memory, such as a Block Oriented Random Access Memory (BORAM), which is disclosed in the U.S. Pat. No. 3,906,455.
Peripheral memory 22 is divided into two track groups 24--24, which each comprise 16 data tracks. An actual data base which is to be searched may comprise several peripheral memories or may comprise a portion of a peripheral memory. In the process of the associative search described in the U.S. Pat. No. 3,906,455, the individual track groups 24--24 comprising a peripheral memory are processed in sequence by the search apparatus which comprises a plurality of subgroup processing elements 28--28 and a combinational processor 34. Combinational selector 26 hence applies each track group 24 in turn to the search apparatus. The data tracks 20 comprising each track group, however, are processed simultaneously.
Each track group 24 is further divided into a number of track subgroups. The data tracks comprising each track subgroup are simultaneously applied to one subgroup processing element 28, which searches the logical records in each data track in accordance with the search specification established by using digital computer 32 and stored in search specification control unit 30.
Each of the subgroup processing elements 28 search a specified number of data tracks. Each subgroup processing element 28 passes the result of its search (i.e., the record in the subgroup best satisfying the search specification) to combinational processor 34. Combinational processor 34 comprises a plurality of individual processors, described in detail in the U.S. Pat. No. 3,906,455, which continuously receive the search results from all the subgroup processing elements 28--28, and the results of processing other subgroups in a particular track group, and then from successive track groups, to determine the best record in each track group, each peripheral memory, and finally in the data base. The best record in the data base is then returned to using computer 32 in response to its original search specification.
In such a search, the value test (which uses either a "least" or "greatest" value operator) can only be performed after all of the range tests have been completed. Since the particular data field against which the value test is to be performed may be any data field in the entire logical record, the apparatus of FIG. 1 must necessarily process each logical record twice to complete an associative search. In the first pass of data, the range tests are completed; in the next pass the value test (if one is specified) is completed. Such a two-pass process necessarily increases the time necessary for a search, and correspondingly decreases the efficiency of the search apparatus.
Additionally, it is often desirable to terminate a search after the first record is retrieved which satisfies the search specification. With the two-pass processor, something more than one complete pass of the data will usually be necessary (i.e. unless there is no value test), even if there existed means for terminating the search when the first record is found.
The problem of two-pass searching is significantly aggravated in the case where more than one record equally satisfies the search specification and all such records must be returned to the using computer. This is referred to in the art as a multiple match. The greater the number of matches in a particular data base, the more time the search requires, due to the necessity of at least one full pass of the data for each record return. Each return requires one complete pass if only range tests are performed, and two complete passes if both range and value tests are performed.
Accordingly, it is a general object of the present invention to provide a subgroup processing element for use in the apparatus of FIG. 1 which overcomes one or more of the disadvantages of the prior art specified above.
It is an object of the present invention to provide such a processing element which is capable of completing both range and value tests in a single pass of the data.
It is another object of the present invention to provide such a processing element which is capable of processing more than one data track simultaneously.
It is a further object of the present invention to increase the speed of a general associative search.
It is yet another object of the present invention to provide such a processing element which can perform a value test on a value field in a given logical record while concurrently maintaining the status of range tests previously performed on range fields in the given logical record.
It is a still further object of the present invention to provide such a processing element which may be successfully used both with conventional peripheral memories and/or Block Oriented Random Access Memories (BORAM).
It is an additional object of the present invention to improve the efficiency of the associative search apparatus.
It is another object of the present invention to provide such a processing element which is capable of terminating a search when a record satisfying the serch specification has been found.
It is a further object of the present invention to provide such a processing element which keeps track of multiple matches.